package demo3;

public class Test {
    public static MySingleList.ListNode getIntersectionNode(
            MySingleList.ListNode headA, MySingleList.ListNode headB) {
        if (headA == null || headB == null) return null;
        //求两个链表的长度
        int lenA = 0;
        int lenB = 0;
        MySingleList.ListNode pl = headA;
        MySingleList.ListNode ps = headB;

        while (pl != null) {
            lenA++;
            pl = pl.next;
        }

        while (ps != null) {
            lenB++;
            ps = ps.next;
        }
        pl = headA;
        ps = headB;
        //差值步 计算
        int len = lenA - lenB;
        if (len < 0 ){
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }

        while (len != 0){
            pl = pl.next;
            len--;
        }
        //说明pl走了差值步 接下来一起走 直到他们两相遇
        while (pl != ps){
            pl = pl.next;
            ps = ps.next;
        }

        return pl;
    }


    //合并两个链表
    public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode head1,
    MySingleList.ListNode head2){
        if (head1 == null) return head2;
        if (head2 == null) return head1;

        MySingleList.ListNode newHead = new MySingleList.ListNode(-1);
        MySingleList.ListNode tmp = newHead;

        while (head1 != null && head2 != null){
            if(head1.val < head2.val) {
                tmp.next = head1;
                tmp = tmp.next;
                head1 = head1.next;
            } else {
                tmp.next = head2;
                tmp = tmp.next;
                head2 = head2.next;
            }
        }
        if (head1 != null) {
            tmp.next = head1;
        }
        if (head2 != null){
            tmp.next = head2;
        }
        return newHead.next;
    }
    public static void main(String[] args) {
        MySingleList mySingleList1 = new MySingleList();//这就是一个单链表
        mySingleList1.addLast(7);
        mySingleList1.addLast(23);
        mySingleList1.addLast(34);
        mySingleList1.addLast(45);
        mySingleList1.addLast(56);
        mySingleList1.disply();
        System.out.println("====================");

        MySingleList mySingleList2 = new MySingleList();//这就是一个单链表
        mySingleList2.addLast(7);
        mySingleList2.addLast(15);
        mySingleList2.addLast(27);
        mySingleList2.disply();
        System.out.println("====================");

        MySingleList.ListNode ret = mergeTwoLists(mySingleList1.head,mySingleList2.head);
        System.out.println("=============");
        mySingleList1.display(ret);

    }

    public static void main1(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addFirst(12);
        mySingleList.addFirst(23);
        mySingleList.addFirst(34);
        mySingleList.addLast(45);
        mySingleList.addLast(56);
        mySingleList.disply();
        mySingleList.addIndex(3,999);
        mySingleList.disply();
        //mySingleList.remove(56);
        mySingleList.reverseList();
        mySingleList.disply();
        MySingleList.ListNode ret = mySingleList.middleNode();

        System.out.println(ret.val);

        try {
            MySingleList.ListNode ret1 = mySingleList.findKthToTail(15);
            System.out.println(ret1.val);
        }catch (NullPointerException e){
            System.out.println("ret的值为null" );
            e.printStackTrace();
        }

    }
}
